home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / BUILD.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  14KB  |  519 lines
  1. /*
  2.  * build.c -- functions associated with building syntax diagrams.
  3.  *
  4.  * SOFTWARE RIGHTS
  5.  *
  6.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  7.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  8.  * company may do whatever they wish with source code distributed with
  9.  * PCCTS or the code generated by PCCTS, including the incorporation of
  10.  * PCCTS, or its output, into commerical software.
  11.  * 
  12.  * We encourage users to develop software with PCCTS.  However, we do ask
  13.  * that credit is given to us for developing PCCTS.  By "credit",
  14.  * we mean that if you incorporate our source code into one of your
  15.  * programs (commercial product, research project, or otherwise) that you
  16.  * acknowledge this fact somewhere in the documentation, research report,
  17.  * etc...  If you like PCCTS and have developed a nice tool with the
  18.  * output, please mention that you developed it using PCCTS.  In
  19.  * addition, we ask that this header remain intact in our source code.
  20.  * As long as these guidelines are kept, we expect to continue enhancing
  21.  * this system and expect to make other tools available as they are
  22.  * completed.
  23.  *
  24.  * ANTLR 1.06
  25.  * Terence Parr
  26.  * Purdue University
  27.  * 1989-1992
  28.  */
  29. #include <stdio.h>
  30. #include "set.h"
  31. #include "syn.h"
  32. #include "hash.h"
  33. #include "generic.h"
  34. #include "dlgdef.h"
  35.  
  36. #define SetBlk(g, t) {                                                \
  37.             ((Junction *)g.left)->jtype = t;                        \
  38.             ((Junction *)g.left)->end = (Junction *) g.right;        \
  39.             ((Junction *)g.right)->jtype = EndBlk;}
  40.  
  41. /* Add the parameter string 'parm' to the parms field of a block-type junction
  42.  * g.left points to the sentinel node on a block.  i.e. g.left->p1 points to
  43.  * the actual junction with its jtype == some block-type.
  44.  */
  45. void
  46. addParm(p,parm)
  47. Node *p;
  48. char *parm;
  49. {
  50.     char *q = malloc( strlen(parm) + 1 );
  51.     require(p!=NULL, "addParm: NULL object\n");
  52.     require(q!=NULL, "addParm: unable to alloc parameter\n");
  53.  
  54.     strcpy(q, parm);
  55.     if ( p->ntype == nRuleRef )
  56.     {
  57.         ((RuleRefNode *)p)->parms = q;
  58.     }
  59.     else if ( p->ntype == nJunction )
  60.     {
  61.         ((Junction *)p)->parm = q;    /* only one parameter allowed on subrules */
  62.     }
  63.     else fatal("addParm: invalid node for adding parm");
  64. }
  65.  
  66. /*
  67.  * Build an action node for the syntax diagram
  68.  *
  69.  * buildAction(ACTION) ::= --o-->ACTION-->o--
  70.  *
  71.  * Where o is a junction node.
  72.  */
  73. Graph
  74. buildAction(action, file, line, is_predicate)
  75. char *action;
  76. int file, line;
  77. int is_predicate;
  78. {
  79.     Junction *j1, *j2;
  80.     Graph g;
  81.     ActionNode *a;
  82.     require(action!=NULL, "buildAction: invalid action");
  83.     
  84.     j1 = newJunction();
  85.     j2 = newJunction();
  86.     a = newActionNode();
  87.     a->action = malloc( strlen(action)+1 );
  88.     require(a->action!=NULL, "buildAction: cannot alloc space for action\n");
  89.     strcpy(a->action, action);
  90.     j1->p1 = (Node *) a;
  91.     a->next = (Node *) j2;
  92.     a->is_predicate = is_predicate;
  93.     g.left = (Node *) j1; g.right = (Node *) j2;
  94.     a->file = file;
  95.     a->line = line;
  96.     return g;
  97. }
  98.  
  99. /*
  100.  * Build a token node for the syntax diagram
  101.  *
  102.  * buildToken(TOKEN) ::= --o-->TOKEN-->o--
  103.  *
  104.  * Where o is a junction node.
  105.  */
  106. Graph
  107. buildToken(text)
  108. char *text;
  109. {
  110.     Junction *j1, *j2;
  111.     Graph g;
  112.     TokNode *t;
  113.     require(text!=NULL, "buildToken: invalid token name");
  114.     
  115.     j1 = newJunction();
  116.     j2 = newJunction();
  117.     t = newTokNode();
  118.     if ( *text == '"' ) {t->label=FALSE; t->token = addTexpr( text );}
  119.     else {t->label=TRUE; t->token = addTname( text );}
  120.     j1->p1 = (Node *) t;
  121.     t->next = (Node *) j2;
  122.     g.left = (Node *) j1; g.right = (Node *) j2;
  123.     return g;
  124. }
  125.  
  126. /*
  127.  * Build a rule reference node of the syntax diagram
  128.  *
  129.  * buildRuleRef(RULE) ::= --o-->RULE-->o--
  130.  *
  131.  * Where o is a junction node.
  132.  *
  133.  * If rule 'text' has been defined already, don't alloc new space to store string.
  134.  * Set r->text to point to old copy in string table.
  135.  */
  136. Graph
  137. buildRuleRef(text)
  138. char *text;
  139. {
  140.     Junction *j1, *j2;
  141.     Graph g;
  142.     RuleRefNode *r;
  143.     RuleEntry *p;
  144.     require(text!=NULL, "buildRuleRef: invalid rule name");
  145.     
  146.     j1 = newJunction();
  147.     j2 = newJunction();
  148.     r = newRNode();
  149.     r->assign = NULL;
  150.     if ( (p=(RuleEntry *)hash_get(Rname, text)) != NULL ) r->text = p->str;
  151.     else r->text = strdup( text );
  152.     j1->p1  = (Node *) r;
  153.     r->next = (Node *) j2;
  154.     g.left = (Node *) j1; g.right = (Node *) j2;
  155.     return g;
  156. }
  157.  
  158. /*
  159.  * Or two subgraphs into one graph via:
  160.  *
  161.  * Or(G1, G2) ::= --o-G1-o--
  162.  *                  |    ^
  163.  *                    v    |
  164.  *                  o-G2-o
  165.  *
  166.  * Set the altnum of junction starting G2 to 1 + altnum of junction starting G1.
  167.  * If, however, the G1 altnum is 0, make it 1 and then
  168.  * make G2 altnum = G1 altnum + 1.
  169.  */
  170. Graph
  171. Or(g1,g2)
  172. Graph g1, g2;
  173. {
  174.     Graph g;
  175.     require(g1.left != NULL, "Or: invalid graph");
  176.     require(g2.left != NULL && g2.right != NULL, "Or: invalid graph");
  177.  
  178.     ((Junction *)g1.left)->p2 = g2.left;
  179.     ((Junction *)g2.right)->p1 = g1.right;
  180.     /* set altnums */
  181.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  182.     ((Junction *)g2.left)->altnum = ((Junction *)g1.left)->altnum + 1;
  183.     g.left = g2.left;
  184.     g.right = g1.right;
  185.     return g;
  186. }
  187.  
  188. /*
  189.  * Catenate two subgraphs
  190.  *
  191.  * Cat(G1, G2) ::= --o-G1-o-->o-G2-o--
  192.  * Cat(NULL,G2)::= --o-G2-o--
  193.  * Cat(G1,NULL)::= --o-G1-o--
  194.  */
  195. Graph
  196. Cat(g1,g2)
  197. Graph g1, g2;
  198. {
  199.     Graph g;
  200.     
  201.     if ( g1.left == NULL && g1.right == NULL ) return g2;
  202.     if ( g2.left == NULL && g2.right == NULL ) return g1;
  203.     ((Junction *)g1.right)->p1 = g2.left;
  204.     g.left = g1.left;
  205.     g.right = g2.right;
  206.     return g;
  207. }
  208.  
  209. /*
  210.  * Make a subgraph an optional block
  211.  *
  212.  * makeOpt(G) ::= --o-->o-G-o-->o--
  213.  *                      |         ^
  214.  *                        v          |
  215.  *                        o-------o
  216.  *
  217.  * Note that this constructs {A|B|...|Z} as if (A|B|...|Z|) was found.
  218.  *
  219.  * The node on the far right is added so that every block owns its own
  220.  * EndBlk node.
  221.  */
  222. Graph
  223. makeOpt(g1)
  224. Graph g1;
  225. {
  226.     Junction *j1,*j2,*p;
  227.     Graph g;
  228.     require(g1.left != NULL && g1.right != NULL, "makeOpt: invalid graph");
  229.  
  230.     j1 = newJunction();
  231.     j2 = newJunction();
  232.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  233.     g = emptyAlt();
  234.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  235.     ((Junction *)g.left)->altnum = ((Junction *)g1.left)->altnum + 1;
  236.     for(p=(Junction *)g1.left; p->p2!=NULL; p=(Junction *)p->p2)
  237.         {;}                                        /* find last alt */
  238.     p->p2 = g.left;                                /* add optional alternative */
  239.     ((Junction *)g.right)->p1 = (Node *)j2;        /* opt alt points to EndBlk */
  240.     g1.right = (Node *)j2;
  241.     SetBlk(g1, aOptBlk);
  242.     j1->p1 = g1.left;                            /* add generic node in front */
  243.     g.left = (Node *) j1;
  244.     g.right = g1.right;
  245.  
  246.     return g;
  247. }
  248.  
  249. /*
  250.  * Make a graph into subblock
  251.  *
  252.  * makeBlk(G) ::= --o-->o-G-o-->o--
  253.  *
  254.  * The node on the far right is added so that every block owns its own
  255.  * EndBlk node.
  256.  */
  257. Graph
  258. makeBlk(g1)
  259. Graph g1;
  260. {
  261.     Junction *j,*j2;
  262.     Graph g;
  263.     require(g1.left != NULL && g1.right != NULL, "makeBlk: invalid graph");
  264.  
  265.     j = newJunction();
  266.     j2 = newJunction();
  267.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  268.     g1.right = (Node *)j2;
  269.     SetBlk(g1, aSubBlk);
  270.     j->p1 = g1.left;                            /* add node in front */
  271.     g.left = (Node *) j;
  272.     g.right = g1.right;
  273.  
  274.     return g;
  275. }
  276.  
  277. /*
  278.  * Make a subgraph into a loop (closure) block -- (...)*
  279.  *
  280.  * makeLoop(G) ::=       |---|
  281.  *                         v   |
  282.  *               --o-->o-->o-G-o-->o--
  283.  *                   |           ^
  284.  *                   v           |
  285.  *                     o-----------o
  286.  *
  287.  * After making loop, always place generic node out front.  It becomes
  288.  * the start of enclosing block.  The aLoopBlk is the target of the loop.
  289.  *
  290.  * Loop blks have TWO EndBlk nodes--the far right and the node that loops back
  291.  * to the aLoopBlk node.  Node with which we can branch past loop == aLoopBegin and
  292.  * one which is loop target == aLoopBlk.
  293.  * The branch-past (initial) aLoopBegin node has end
  294.  * pointing to the last EndBlk node.  The loop-target node has end==NULL.
  295.  *
  296.  * Loop blocks have a set of locks (from 1..LL_k) on the aLoopBlk node.
  297.  */
  298. Graph
  299. makeLoop(g1)
  300. Graph g1;
  301. {
  302.     Junction *back, *front, *begin;
  303.     Graph g;
  304.     require(g1.left != NULL && g1.right != NULL, "makeLoop: invalid graph");
  305.  
  306.     back = newJunction();
  307.     front = newJunction();
  308.     begin = newJunction();
  309.     g = emptyAlt();
  310.     ((Junction *)g1.right)->p2 = g1.left;        /* add loop branch to G */
  311.     ((Junction *)g1.right)->p1 = (Node *) back;    /* add node to G at end */
  312.     ((Junction *)g1.right)->jtype = EndBlk;        /* mark 1st EndBlk node */
  313.     ((Junction *)g1.left)->jtype = aLoopBlk;    /* mark 2nd aLoopBlk node */
  314.     ((Junction *)g1.left)->end = (Junction *) g1.right;
  315.     ((Junction *)g1.left)->lock = makelocks();
  316.     ((Junction *)g1.left)->pred_lock = makelocks();
  317.     g1.right = (Node *) back;
  318.     begin->p1 = (Node *) g1.left;
  319.     g1.left = (Node *) begin;
  320.     begin->p2 = (Node *) g.left;                /* make bypass arc */
  321.     ((Junction *)g.right)->p1 = (Node *) back;
  322.     SetBlk(g1, aLoopBegin);
  323.     front->p1 = g1.left;                        /* add node to front */
  324.     g1.left = (Node *) front;
  325.  
  326.     return g1;
  327. }
  328.  
  329. /*
  330.  * Make a subgraph into a plus block -- (...)+ -- 1 or more times
  331.  *
  332.  * makeLoop(G) ::=     |---|
  333.  *                     v   |
  334.  *               --o-->o-G-o-->o--
  335.  *
  336.  * After making loop, always place generic node out front.  It becomes
  337.  * the start of enclosing block.  The aPlusBlk is the target of the loop.
  338.  *
  339.  * Plus blks have TWO EndBlk nodes--the far right and the node that loops back
  340.  * to the aPlusBlk node.
  341.  *
  342.  * Plus blocks have a set of locks (from 1..LL_k) on the aPlusBlk node.
  343.  */
  344. Graph
  345. makePlus(g1)
  346. Graph g1;
  347. {
  348.     Junction *j2, *j3;
  349.     require(g1.left != NULL && g1.right != NULL, "makePlus: invalid graph");
  350.  
  351.     j2 = newJunction();
  352.     j3 = newJunction();
  353.     if ( ((Junction *)g1.left)->altnum == 0 ) ((Junction *)g1.left)->altnum = 1;
  354.     ((Junction *)g1.right)->p2 = g1.left;        /* add loop branch to G */
  355.     ((Junction *)g1.right)->p1 = (Node *) j2;    /* add node to G at end */
  356.     ((Junction *)g1.right)->jtype = EndBlk;        /* mark 1st EndBlk node */
  357.     g1.right = (Node *) j2;
  358.     SetBlk(g1, aPlusBlk);
  359.     ((Junction *)g1.left)->lock = makelocks();
  360.     ((Junction *)g1.left)->pred_lock = makelocks();
  361.     j3->p1 = g1.left;                            /* add node to front */
  362.     g1.left = (Node *) j3;
  363.     
  364.     return g1;
  365. }
  366.  
  367. /*
  368.  * Return an optional path:  --o-->o--
  369.  */
  370. Graph
  371. emptyAlt()
  372. {
  373.     Junction *j1, *j2;
  374.     Graph g;
  375.  
  376.     j1 = newJunction();
  377.     j2 = newJunction();
  378.     j1->p1 = (Node *) j2;
  379.     g.left = (Node *) j1;
  380.     g.right = (Node *) j2;
  381.     
  382.     return g;
  383. }
  384.  
  385. /* N o d e  A l l o c a t i o n */
  386.  
  387. TokNode *
  388. newTokNode()
  389. {
  390.     static TokNode *FreeList = NULL;
  391.     TokNode *p, *newblk;
  392.  
  393.     if ( FreeList == NULL )
  394.     {
  395.         newblk = (TokNode *)calloc(TokenBlockAllocSize, sizeof(TokNode));
  396.         if ( newblk == NULL )
  397.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  398.         for (p=newblk; p<&(newblk[TokenBlockAllocSize]); p++)
  399.         {
  400.             p->next = (Node *)FreeList;    /* add all new token nodes to FreeList */
  401.             FreeList = p;
  402.         }
  403.     }
  404.     p = FreeList;
  405.     FreeList = (TokNode *)FreeList->next;/* remove a Junction node */
  406.     p->next = NULL;                        /* NULL the ptr we used */
  407.  
  408.     p->ntype = nToken;
  409.     p->rname = CurRule;
  410.     p->file = CurFile;
  411.     p->line = zzline;
  412.     
  413.     return p;
  414. }
  415.  
  416. RuleRefNode *
  417. newRNode()
  418. {
  419.     static RuleRefNode *FreeList = NULL;
  420.     RuleRefNode *p, *newblk;
  421.  
  422.     if ( FreeList == NULL )
  423.     {
  424.         newblk = (RuleRefNode *)calloc(RRefBlockAllocSize, sizeof(RuleRefNode));
  425.         if ( newblk == NULL )
  426.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  427.         for (p=newblk; p<&(newblk[RRefBlockAllocSize]); p++)
  428.         {
  429.             p->next = (Node *)FreeList;    /* add all new rref nodes to FreeList */
  430.             FreeList = p;
  431.         }
  432.     }
  433.     p = FreeList;
  434.     FreeList = (RuleRefNode *)FreeList->next;/* remove a Junction node */
  435.     p->next = NULL;                        /* NULL the ptr we used */
  436.  
  437.     p->ntype = nRuleRef;
  438.     p->rname = CurRule;
  439.     p->file = CurFile;
  440.     p->line = zzline;
  441.     p->astnode = ASTinclude;
  442.     
  443.     return p;
  444. }
  445.  
  446. Junction *
  447. newJunction()
  448. {
  449.     static Junction *FreeList = NULL;
  450.     Junction *p, *newblk;
  451.  
  452.     if ( FreeList == NULL )
  453.     {
  454.         newblk = (Junction *)calloc(JunctionBlockAllocSize, sizeof(Junction));
  455.         if ( newblk == NULL )
  456.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  457.         for (p=newblk; p<&(newblk[JunctionBlockAllocSize]); p++)
  458.         {
  459.             p->p1 = (Node *)FreeList;    /* add all new Junction nodes to FreeList */
  460.             FreeList = p;
  461.         }
  462.     }
  463.     p = FreeList;
  464.     FreeList = (Junction *)FreeList->p1;/* remove a Junction node */
  465.     p->p1 = NULL;                        /* NULL the ptr we used */
  466.  
  467.     p->ntype = nJunction;    p->visited = 0;
  468.     p->jtype = Generic;
  469.     p->rname = CurRule;
  470.     p->file = CurFile;
  471.     p->line = zzline;
  472.     p->fset = (set *) calloc(LL_k+1, sizeof(set));
  473.     require(p->fset!=NULL, "cannot allocate fset in newJunction");
  474.  
  475.     return p;
  476. }
  477.  
  478. ActionNode *
  479. newActionNode()
  480. {
  481.     static ActionNode *FreeList = NULL;
  482.     ActionNode *p, *newblk;
  483.  
  484.     if ( FreeList == NULL )
  485.     {
  486.         newblk = (ActionNode *)calloc(ActionBlockAllocSize, sizeof(ActionNode));
  487.         if ( newblk == NULL )
  488.             fatal(eMsg1("out of memory while building rule '%s'",CurRule));
  489.         for (p=newblk; p<&(newblk[ActionBlockAllocSize]); p++)
  490.         {
  491.             p->next = (Node *)FreeList;    /* add all new Action nodes to FreeList */
  492.             FreeList = p;
  493.         }
  494.     }
  495.     p = FreeList;
  496.     FreeList = (ActionNode *)FreeList->next;/* remove a Junction node */
  497.     p->next = NULL;                        /* NULL the ptr we used */
  498.     
  499.     p->ntype = nAction;
  500.     return p;
  501. }
  502.  
  503. /*
  504.  * allocate the array of locks (1..LL_k) used to inhibit infinite recursion.
  505.  * Infinite recursion can occur in (..)* blocks, FIRST calcs and FOLLOW calcs.
  506.  * Therefore, we need locks on aLoopBlk, RuleBlk, EndRule nodes.
  507.  *
  508.  * if ( lock[k]==TRUE ) then we have been here before looking for k tokens
  509.  * of lookahead.
  510.  */
  511. char *
  512. makelocks()
  513. {
  514.     char *p = (char *) calloc(LL_k+1, sizeof(char));
  515.     require(p!=NULL, "cannot allocate lock array");
  516.     
  517.     return p;
  518. }
  519.